package th.retrofit.lib;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution126 {

    public List<List<String>> findLadders(String beginWord,
                                          String endWord,
                                          List<String> wordList) {
        List<List<String>> result = new LinkedList<>();
        Set<String> dictionary = new HashSet<>(wordList);
        if (!dictionary.contains(endWord)) return result;
        Map<String, List<String>> map = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        dictionary.remove(beginWord);
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        int level = 1;
        boolean found = false;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                String curWord = queue.poll();
                char[] charArr = curWord.toCharArray();
                int arrSize = charArr.length;
                for (int j = 0; j < arrSize; j++) {
                    char origin = charArr[j];
                    for (char k = 'a'; k <= 'z' ; k++) {
                        charArr[j] = k;
                        String nextWord = String.valueOf(charArr);
                        if (steps.containsKey(nextWord) && level == steps.get(nextWord)) {
                            map.get(nextWord).add(curWord);
                        }
                        if (!dictionary.contains(nextWord)) {
                            continue;
                        }
                        dictionary.remove(nextWord);
                        steps.put(nextWord, level);
                        queue.offer(nextWord);
                        map.putIfAbsent(nextWord, new LinkedList<>());
                        map.get(nextWord).add(curWord);
                        if (nextWord.equals(endWord)) {
                            found = true;
                            break;
                        }
                    }
                    charArr[j] = origin;
                }
            }
            level++;
            if (found) {
                break;
            }
        }
        if (found) {
            Deque<String> deque = new LinkedList<>();
            deque.offer(endWord);
            dfs(map, deque, beginWord, endWord, result);
        }
        return result;
    }

    private void dfs(Map<String, List<String>> from, Deque<String> path, String beginWord, String cur, List<List<String>> res) {
        if (cur.equals(beginWord)) {
            res.add(new LinkedList<>(path));
            return;
        }
        List<String> preWords = from.get(cur);
        for (String pre : preWords) {
            path.offerFirst(pre);
            dfs(from, path, beginWord, pre, res);
            path.pollFirst();
        }
    }

    public static void main(String[] args) {
        String[] wordList = new String[]{"hot","dot","dog","lot","log","cog"};
        String beginWord = "hit";
        String endWord = "cog";
        List<List<String>> results = new Solution126().findLadders(beginWord, endWord, Arrays.asList(wordList));
        results.forEach(it -> {
            it.forEach(that -> {
                System.out.print(that);
                System.out.print(",");
            });
            System.out.println();
        });
    }

}
